package com.hdu.other.dp.treeDP;


import java.util.ArrayList;
import java.util.List;

public class lc2477 {
    class Solution {
        int[] size;
        int[] cost;
        public long minimumFuelCost(int[][] roads, int seats) {

            int n = roads.length + 1;
            List<List<Integer>> g = new ArrayList<>();
            for (int i = 0; i < n; i++)
                g.add(new ArrayList<>());
            for (int[] r : roads) {
                int from = r[0];
                int to = r[1];
                g.get(from).add(to);
                g.get(to).add(from);
            }
            size = new int[n];
            cost = new int[n];
            f(g, 0, -1, seats);
            return cost[0];
        }

        void f(List<List<Integer>> g, int x, int parent, int seats) {
            if (g.get(x).isEmpty()) {
                return;
            }
            size[x] = 1;
            for (int next : g.get(x)) {
                if (next != parent) {
                    f(g, next, x, seats);
                    size[x] += size[next];
                    cost[x] += cost[next] + (size[next] + seats - 1) / seats;
                }
            }
        }
    }
}
